package leetcode_701_800;

public class LeeCode_765 {
    public static void main(String[] args) {
        System.out.println(minSwapsCouples(new int[]{0, 2, 1, 2}));
    }
    private static int minSwapsCouples(int[] row) {
        int n = row.length / 2;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < row.length; i += 2) {
            unionFind.union(row[i] / 2, row[i + 1] / 2);
        }
        return n - unionFind.count;
    }
    private static class UnionFind{
        int[] parent;
        int count;

        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
            this.count = n;
        }

        int find(int x){
            if (parent[x] == x){
                return x;
            }else {
                return find(parent[x]);
            }
        }

        void union(int x, int y){
            int xr = find(x);
            int xy = find(y);
            if (xr != xy){
                count--;
            }
            parent[xr] = xy;
        }
    }
}
